# !/usr/bin/env python
# -*- coding: utf-8 -*-

# 归并排序
# 基本思想：将待排序的数组元素 按下标的一定增量分组 ，分成多个子序列，然后对各个子序列进行直接插入排序算法排序；
# 然后依次缩减增量再进行排序，直到增量为1时，进行最后一次直接插入排序，排序结束。

# 时间复杂度:O(nlogn)
# 空间复杂度:最好(nlogn)/2,最坏(nlogn)-n+1,平均O(n)
# 稳定性:稳定
from sort.arr_util import random_scale_arr


def merge_sort(num_arr):
    part(num_arr, 0, len(num_arr) - 1)


def part(num_arr, start, end):
    # print(str(start) + "-" + str(end), end="\n")
    if start == end:
        return
    mid = start + int((end - start) / 2)
    part(num_arr, start, mid)
    part(num_arr, mid + 1, end)
    merge(num_arr, start, end, mid)


def merge(num_arr, start, end, mid):
    tmp_list = num_arr[start:end + 1]
    index = 0
    l_index = start
    r_index = mid + 1
    while l_index <= mid and r_index <= end:
        if num_arr[l_index] <= num_arr[r_index]:
            tmp_list[index] = num_arr[l_index]
            l_index += 1
        else:
            tmp_list[index] = num_arr[r_index]
            r_index += 1
        index += 1
    while l_index <= mid:
        tmp_list[index] = num_arr[l_index]
        l_index += 1
        index += 1
    while r_index <= end:
        tmp_list[index] = num_arr[r_index]
        r_index += 1
        index += 1
    for i in range(0, len(tmp_list)):
        num_arr[start + i] = tmp_list[i]


if __name__ == '__main__':
    # arr = [1, 2, 5, 7, 6, 5, 4]
    # arr.sort()
    arr = [4, 2, 5, 1]
    merge_sort(arr)
    print(arr)
    arr2 = random_scale_arr(20, 500)
    merge_sort(arr2)
    print(arr2)
